package 算法.动态规划;

public class JZ70矩形覆盖 {
    //递归
    //规律： f(n) = f(n-1) + f(n-2)
    public int rectCover(int target) {
        //约定 n == 0 时，输出 0, 1时也只有一种
        if(target <= 2)
            return target;
        //f(n-1)+f(n-2)
        return rectCover(target - 1) + rectCover(target - 2);
    }

    //动态规划
    public int rectCover1(int target){
        if(target<=1)
            return target;
        int[] dp = new int[target + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= target; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return  dp[target];
    }

    public int rectCover2(int target) {
        if(target<=1) return  target;
        int x = 1;
        int y = 1;
        int z = 1;
        for(int i=2;i<=target;i++){
            z = x + y;
            x = y;
            y = z;
        }
        return z;
    }
}
